package sort;

/**
 * 归并排序，时间复杂度为
 */
public class MergeSort {
    public static <E extends Comparable<E>> void sort(E[] array) {
        E[] tmp = (E[]) new Comparable[array.length];
        mSort(array, tmp, 0, array.length - 1);
    }

    /**
     * 辅助归并函数
     * 
     * @param <E>
     * @param array
     */
    public static <E extends Comparable<E>> void mSort(E[] array, E[] tmp, int left, int right) {
        int center;
        if (left < right) {
            center = (left + right) / 2;
            mSort(array, tmp, left, center);
            mSort(array, tmp, center + 1, right);
            merge(array, tmp, left, center + 1, right);
        }
    }

    /**
     * 辅助归并函数
     * 
     * @param <E>
     * @param array
     * @param tmp      临时数组
     * @param left     左数组起点
     * @param right    右数组起点
     * @param rightEnd 右数组终点
     */
    public static <E extends Comparable<E>> void merge(E[] array, E[] tmp, int left, int right, int rightEnd) {
        int leftEnd = right - 1;
        int target = left;
        int count = rightEnd - left + 1;
        while (left <= leftEnd && rightEnd >= right) {
            if (array[left].compareTo(array[right]) < 0) {
                tmp[target] = array[left];
                left++;
            } else {
                tmp[target] = array[right];
                right++;
            }
            target++;
        }
        while (left <= leftEnd) {
            tmp[target] = array[left];
            target++;
            left++;
        }

        while (right <= rightEnd) {
            tmp[target] = array[right];
            target++;
            right++;
        }

        for (int i = 0; i < count; i++, rightEnd--) {
            array[rightEnd] = tmp[rightEnd];
        }
    }
}